int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] > a[mid])
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
	else
	{
		if (a[begin] > a[end])
		{
			return begin;
		}
		else if (a[mid] > a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}

}
//hoare
int partSort1(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[begin]);

	int left = begin;
	int right = end;
	int keyi = begin;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[keyi]);

	keyi = left;
	return keyi;
}

//hoare优化:挖坑法  思想都是关键数大于左边小于右边,效率差不多
int partSort2(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[begin]);

	int key = a[begin];
	int hole = begin;

	while (begin < end)
	{
		//右边找小,填到坑位,更新坑位
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;

		//左边找大,,填到坑位,更新坑位
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = key;
	return hole;
}

//hoare优化:双指针法
int partSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[begin]);

	int prev = begin;
	int cur = begin + 1;
	int key = begin;
	/*while (cur <=end)
	{
		if (a[cur] >= a[key])
		{
			cur++;
		}
		else
		{
			prev++;
			if (prev != cur)
			{
				swap(&a[prev], &a[cur]);
			}
			cur++;
		}
	}
	swap(&a[key], &a[prev]);
	return prev;*/

	//优化:
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != end)
			swap(&a[prev], &a[cur]);
		++cur;
	}
	swap(&a[key], &a[prev]);
	return prev;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{

		//int keyi = pratSort1(a, begin, end);
		int keyi = partSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}
